Connected Component Labeling (CCL) is an important step in patternrecognition and image processing. It assigns labels to the pixels such thatadjacent pixels sharing the same features are assigned the same label.Typically, CCL requires several passes over the data. We focus on two-passtechnique where each pixel is given a provisional label in the first passwhereas an actual label is assigned in the second pass. We present a scalable parallel two-pass CCL algorithm, called PAREMSP, whichemploys a scan strategy and the best union-find technique called REMSP, whichuses REM's algorithm for storing label equivalence information of pixels in a2-D image. In the first pass, we divide the image among threads and each threadruns the scan phase along with REMSP simultaneously. In the second phase, weassign the final labels to the pixels. As REMSP is easily parallelizable, weuse the parallel version of REMSP for merging the pixels on the boundary. Ourexperiments show the scalability of PAREMSP achieving speedups up to $20.1$using $24$ cores on shared memory architecture using OpenMP for an image ofsize $465.20$ MB. We find that our proposed parallel algorithm achieves linearscaling for a large resolution fixed problem size as the number of processingelements are increased. Additionally, the parallel algorithm does not make useof any hardware specific routines, and thus is highly portable.
展开▼
